The present invention relates to a pipelined Fast Fourier Transform processor as is described in the non-characteristic part of claim 1.
Such a pipelined Fast Fourier Transform processor is already known in the art, e.g. from the published European Patent Application "Pipelined Fast Fourier Transform processor", publication number 0478128A2. Therein, a pipelined Fast Fourier Transform processor is described, including a cascade of four Butterfly Arithmetic Units, abbreviated with BAU in the prior art document. Each of these units processes data received at its input ports and generates a pair of output signals, which are consecutively applied to the input ports of the next stage, or in case of the final fourth stage, to memory locations via a multiplexer. Within each unit, the output signals , before being delivered to the next unit, are temporarily stored in four registers. Two of the cascaded units of the prior art document can thus be considered as corresponding to the first and second arithmetic unit of the present invention, whereas the four registers included in the first stage of the prior art, can be considered as corresponding to the scratch memory of the pipelined Fast Fourier Transform processor of the invention. The multiplexer together with the memory locations of the prior art thereby constitute the memory arrangement included within the Fast Fourier Transform processor of the invention.
The units of the prior art processor all include the same building blocks for performing a radix-two-operation Fast Fourier Transform, hereafter abbreviated by FFT, operation on their respective input data, as is explained in the prior art document.
For some applications, such as for instance in Very High Speed Digital Subscriber Line transmission and receiving modules, a 512 point real FFT, is to be performed in less than 1024 clock cycles, whereby during each cycle one data point is read from the memory arrangement into the first arithmetic unit. As is well known by a person skilled in the art, performing a 512 point real FFT in fact corresponds to performing a 256 point complex FFT, taken into account some changes such as these explained for instance in the US Patent nr. 5,633,817 "Fast Fourier Transform Dedicated Processor". However, when performing a 256 point complex FFT using the architecture of the prior art processor, too much multipliers are needed for obtaining the target timing restrictions. Indeed, for performing a 256 point complex FFT, 8 of the prior art radix-2 type BAU's have to be passed. Using only two of these BAU's or stages in cascade, while passing 4 times through the pipeline, already consumes more than 4.times.256 clock cycles for reading input data from the memory arrangement to the first BAU, definitely already exceeding the target timing restrictions. Therefore, for complying with the timing restrictions, minimum three of these BAU's are required to be put in the cascade. Since each prior art BAU includes 4 multipliers, as is clear from FIG. 2 of the prior art document, in total thus 12 multipliers have to be included in the processor. Taken however into account the state of the art of the integrated circuit technology at the time of the invention, a total of 12 multipliers would result in a too large integrated circuit area.